package org.everyday;

import com.common.TreeNode;

/**
 * @Author: Tang World
 * @Date: 10/9/2022 上午2:55
 */
public class L669M {
    public static void main(String[] args) {
        TreeNode root = TreeNode.buildTree(new Integer[]{3, 0, 4, null, 2, null, null, 1});
        TreeNode treeNode = new L669M().trimBST(root, 1, 3);
        System.out.println(treeNode);
    }

    public TreeNode trimBST(TreeNode root, int low, int high) {
        // 递归，自顶向下，当遇到不满足条件时，返回 修建好的子树
        if (root == null) return null;
        if (root.val < low) {
            return trimBST(root.right, low, high);
        }
        if (root.val > high) {
            return trimBST(root.left, low, high);
        }
        root.left = trimBST(root.left, low, high);
        root.right = trimBST(root.right, low, high);
        return root;
    }
}
